package algorithm.swordoff;

/**
 * 二叉搜索树的第k大节点
 *
 * 中序遍历的逆序是递减序列
 * 用一个最小堆保存前K大的数字
 */

public class SQ54 {

    int index = -1;
    int count = 0;
    int kthNodeVal;

    public int kthLargest(TreeNode root, int k) {
        countNodes(root);
        postorder(root, k);
        return kthNodeVal;
    }

    private void countNodes(TreeNode n) {
        if (n == null) return;
        countNodes(n.left);
        count++;
        countNodes(n.right);
    }

    private void postorder(TreeNode n, int k) {
        if (n == null) return;

        postorder(n.left, k);
        index++;
        if (count-index == k) {
            kthNodeVal = n.val;
        }
        postorder(n.right, k);
    }

    public static void main(String[] args) {
        SQ54 sq54 = new SQ54();
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        node3.left = node1;
        node1.right = node2;
        node3.right = node4;
        sq54.kthLargest(node3, 1);
    }

}
